1918D - Blocking Elements - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long int
#define pb push_back
#define size(a) a.size()
#define traverse(a) for (int i = 0; i < size(a); i++)
#define mod 1000000007
#define cdv vector<vector<int>>
#define cv vector<int>
#define range(v) v.begin(), v.end()
#define loop(i, a, b) for (int i = a; i <= b; i++)
#define rloop(i, a, b) for (int i = a; i >= b; i--)
#define ff first
#define ss second

bool check(int val, cv &v)
{
    int n = size(v) - 1;
    cdv dp(n + 1, cv(2, 0));
    map<int, int> mp;
    mp[0] = 0;
    loop(i, 1, n)
    {
        dp[i][1] = v[i] - v[i - 1] + min(dp[i - 1][0], dp[i - 1][1]);
        while (1){
            auto it = mp.end();
            it--;
            if (it->ss >= dp[i][1]) mp.erase(it);
            else break;
        }
        mp[v[i]] = dp[i][1];
        dp[i][0] = mp.lower_bound(v[i] - val)->ss;
    }
    if (min(dp[n][0], dp[n][1]) <= val) return 1;
    return 0;
}

int bs(int l, int r, cv &v)
{
    if (l == r) return l;
    int mid = (l + r) / 2;
    if (check(mid, v)) return bs(l, mid, v);
    else return bs(mid + 1, r, v);
}

void fun()
{
    int ans = 0;
    int n; cin >> n;
    map<int, int> mp;
    cv v(n + 1, 0);
    traverse(v)
    {
        if (i == 0) continue;
        cin >> v[i];
        v[i] += v[i - 1];
    }
    cout << bs(0, 1e14, v) << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    while (n--)
        fun();
}